package vip.xumy.learning.algorithm;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import vip.xumy.learning.pojo.ListNode;

/**
 * @author:mengyxu 
 * @date:2020年11月19日
 */

public class Exercises201119 {

	/**
	 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
	 * 
	 * 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。
	 */
	public static void moveZero(int[] nums) {
		if (nums == null || nums.length < 2) {
			return;
		}
		int idx = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != 0) {
				int tmp = nums[i];
				nums[i] = nums[idx];
				nums[idx++] = tmp;
			}
		}
	}

	/**
	 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
	 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
	 * 
	 * 示例: 给定 nums = [2, 7, 11, 15], target = 9 , 返回 [0, 1]
	 */
	public static int[] getIndexBySun(int[] nums, int target) {
		if (nums == null || nums.length < 2) {
			return new int[] { -1, -1 };
		}
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(nums[i])) {
				return new int[] { map.get(nums[i]), i };
			} else {
				map.put(target - nums[i], i);
			}
		}
		return new int[] { -1, -1 };
	}

	/**
	 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
	 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
	 * 
	 * 示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
	 */
	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode root = null;
		ListNode tmp = null;
		int sum = 0;
		while (l1 != null || l2 != null) {
			if (l1 != null) {
				sum += l1.val;
				l1 = l1.next;
			}
			if (l2 != null) {
				sum += l2.val;
				l2 = l2.next;
			}
			ListNode l = new ListNode(sum % 10);
			if (root == null) {
				root = l;
				tmp = l;
			} else {
				tmp.next = l;
				tmp = l;
			}
			sum /= 10;
		}
		if (sum > 0) {
			tmp.next = new ListNode(sum);
		}
		return root;
	}

	/**
	 * 对链表进行插入排序。 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
	 * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
	 * 
	 * 插入排序算法： 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
	 * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 重复直到所有输入数据插入完为止。
	 * 
	 * 示例 1： 输入: 4->2->1->3 输出: 1->2->3->4; 示例 2： 输入: -1->5->3->4->0 输出:
	 * -1->0->3->4->5
	 */
	public static ListNode insertionSortList(ListNode head) {
		ListNode root = new ListNode(0);
		while (head != null) {
			ListNode nextHead = head.next;
			ListNode tmp = root;
			ListNode begin = root.next;
			if (begin == null) {
				tmp.next = head;
				head.next = null;
			}
			boolean b = true;
			while (begin != null) {
				if (head.val < begin.val) {
					tmp.next = head;
					tmp.next.next = begin;
					b = false;
					break;
				}
				tmp = begin;
				begin = begin.next;
			}
			if (b) {
				tmp.next = head;
				head.next = null;
			}
			head = nextHead;
		}
		return root.next;
	}

	/**
	 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
	 * 
	 * 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
	 * 
	 * 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
	 * 
	 * 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串
	 * 的长度，"pwke" 是一个子序列，不是子串。
	 */
	public static int lengthOfLongestSubstring(String s) {
		if(s == null || s.equals("")) {
			return 0;
		}
		Set<Character> set = new HashSet<>();
		int max = 0;
		int count = 0;
		int idx = 0;
		int len = s.length();
		for (int i = 0; i < len; i++) {
			Character c = s.charAt(i);
			if(set.contains(c)) {
				max = max > count ? max : count;
				count = 0;
				set.clear();
				i = s.indexOf(c, idx);
				idx = i+1;
				continue;
			}
			set.add(c);
			count ++;
		}
		return max > count ? max : count;
	}

	
	
}
